// 题目描述
// 583. 两个字符串的删除操作
// 难度
// 中等
// 599
// 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
// 每步 可以删除任意一个字符串中的一个字符。
//   示例 1：
// 输入: word1 = "sea", word2 = "eat"
// 输出: 2
// 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
// 示例  2:
// 输入：word1 = "leetcode", word2 = "etco"
// 输出：4
//   提示：
// 1 <= word1.length, word2.length <= 500
// word1 和 word2 只包含小写英文字母
// 通过次数128,605提交次数192,891
// https://leetcode.cn/problems/delete-operation-for-two-strings/

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const len1 = word1.length
  const len2 = word2.length

  const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0))

  for (let i = 0; i <= len1; i++) {
    dp[i][0] = i
  }
  for (let i = 0; i <= len2; i++) {
    dp[0][i] = i
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] // 一样就不删了
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // 删除 word1[i - 1]
          dp[i][j - 1] + 1  // 删除 word2[j - 1]
        )
      }
    }
  }

  return dp[len1][len2]
}

console.log(
  minDistance(
    "sea", "eat"
  )
)

